package com.da.javatest.leetCode;

/**
 * @author chenlida
 * @date 2019/3/5 10:49
 * @description
 */
public class Code19 {
    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(2);
        System.out.println(new Code19().removeNthFromEnd(l1, 2));
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        int size = getSize(head, 0);
        //删除第一个
        if (size == n) {
            return head.next;
        }
        //删除中间节点
        removeNode(head, size - n, 1);
        return head;
    }

    private int getSize(ListNode node, int size) {
        if (node != null) {
            return getSize(node.next, size + 1);
        }
        return size;
    }

    private void removeNode(ListNode head, int index, int start) {
        if (index == start) {
            head.next = head.next.next;
            return;
        }
        removeNode(head.next, index, start + 1);
    }

    //快慢指针
    //public ListNode removeNthFromEnd(ListNode head, int n) {
    //    ListNode fast = head, slow = head;
    //    while (n > 0) {
    //        fast = fast.next;
    //        n--;
    //    }
    //    if (fast == null) { return slow.next; }
    //    while (fast.next != null) {
    //        fast = fast.next;
    //        slow = slow.next;
    //    }
    //    slow.next = slow.next.next;
    //    return head;
    //}
}
